package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type Node struct {
	treeNode *TreeNode
	depth    int
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	stack := []*Node{
		{root, 1},
	}
	depth := 0
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		if node != nil && node.treeNode != nil {
			if node.depth > depth {
				depth = node.depth
			}
			stack = append(stack, &Node{node.treeNode.Left, node.depth + 1})
			stack = append(stack, &Node{node.treeNode.Right, node.depth + 1})
		}
	}
	return depth
}

func main() {
	root := &TreeNode{Val: 3}
	n1 := &TreeNode{Val: 9}
	n2 := &TreeNode{Val: 20}
	n3 := &TreeNode{Val: 15}
	n4 := &TreeNode{Val: 7}
	root.Left = n1
	root.Right = n2
	n2.Left = n3
	n2.Right = n4
	println(maxDepth(root))

}
